package com.njupt.Tree;

import java.util.*;

/**
 * @Author: wujiaming
 * @CreateTime: 2024/12/6 20:00
 * @Description: 501. 二叉搜索树中的众数
 * @Version: 1.0
 */


public class FindMode {

    public int[] findMode(TreeNode root) {
        Map<Integer, Integer> resultMap = new HashMap<>();

        traverse(root,resultMap);
        List<Map.Entry<Integer, Integer>> entries = new ArrayList<>(resultMap.entrySet());
        Collections.sort(entries,(e1,e2)-> e2.getValue()-e1.getValue());

        List<Integer> results = new ArrayList<>();
        for (int i = 0; i < entries.size(); i++) {
            if(entries.get(i).getValue() == entries.get(0).getValue()){
                results.add(entries.get(i).getKey());
            }
        }
        return results.stream().mapToInt(Integer::intValue).toArray();
    }

    private void traverse(TreeNode root, Map<Integer, Integer> resultMap) {
        if(root == null) return;

        traverse(root.left,resultMap);
        resultMap.put(root.val,resultMap.getOrDefault(root.val,0)+1);
        traverse(root.right,resultMap);
    }

    public static void main(String[] args) {
        TreeNode root = new TreeNode(0);
//        root.right = new TreeNode(2);
//        root.right.left = new TreeNode(2);

//        TreeNode root = new TreeNode(6);
//        root.left = new TreeNode(2);
//        root.right = new TreeNode(8);
//        root.left.left = new TreeNode(0);
//        root.left.right = new TreeNode(4);
//        root.left.right.left = new TreeNode(2);
//        root.left.right.right = new TreeNode(6);
//
//        root.right.left = new TreeNode(7);
//        root.right.right = new TreeNode(9);

        FindMode test = new FindMode();
        int[] mode = test.findMode(root);
        System.out.println(Arrays.toString(mode));
    }
}
